Conventional methods for subdividing one spatial region into multiple smaller regions include both manual and automatic methods. Manual methods involve decisions by humans about where boundaries between sub-regions will fall. In automated methods, boundaries are set by processes performed by machines, such as digital computers.
Boundary-drawing activities are known to be motivated by any of numerous different concerns. For instance, in the field of geospatial information systems (GIS), it is desirable to have the ability to automatically organize management zones based on arbitrary spatial properties. That is, regions that have similar properties and are in the same general contiguous area may be grouped into a single “zone.” For example, in the case of a farmer's field, it may be desirable to group crops of a particular type into a single zone. More particularly, where a farmer uses aerial and/or satellite imagery to observe conditions in the field, multiple images are sometimes merged into a single, continuous visualization.
However, where there is a large homogeneous region, the result may be a single zone that is too large to efficiently manage on its own. Accordingly, it is often desirable to subdivide one zone into multiple smaller zones, to facilitate more effective management. However, the time and effort necessary to manually subdivide GIS zones can be large. Moreover, with an ever-increasing volume of data being made available, the need for automation is persistently increasing. It is also difficult to divide the space into sub-regions of equal parts, each having the minimum perimeter length.
Another class of problems is known to arise in the domain of democratic politics, where much attention has been dedicated to studying the practice of gerrymandering, by which those empowered to set boundaries for electoral districts are believed to seek to influence electoral outcomes by reshaping the electoral districts within a state. Critics of gerrymandering have drawn attention to the elongated and contorted shapes of electoral districts said to characterize the practice. Some have argued that principles of fairness and sound public policy weigh in favor of grouping voters together with their neighbors, rather than permitting politicians to create voting districts that are hand-picked from across far-flung parts of the state. However, the boundaries of a state, like the boundaries of a farmer's field, are not always defined by simple shapes or straight lines. Moreover, quantities of interest (e.g., eligible voter populations, crop varieties, etc.) are not always distributed evenly.
FIG. 1 illustrates a region 101 having an arbitrary shape. In some contexts, it is desirable to subdivide arbitrarily shaped regions such as the region 101 into multiple sub-regions. It is likewise desirable to ensure that no sub-region exceeds a predetermined area size, e.g., a given number of pixels to be displayed on a digital display, or a manageable area for a farmer's crops. It is also desirable that the resulting sub-regions are compact, having as minimal a perimeter as possible. After the region 101 is subdivided into more manageable sub-regions, and a user may be enabled to more effectively review, analyze, and act on information conveyed in the data.
FIG. 2 illustrates one conventional method (the “naive” method) for subdividing region 101, wherein region 101 is repeatedly divided into sub-regions oriented along a single axis, such as the x- or y-axis. In particular, in FIG. 2, region 101 is split into vertical sub-regions 201a, 201b, 201c . . . 201n, where n is an arbitrary integer. In one version of the naive method as shown in FIG. 2, the first sub-region 201a, and each succeeding sub-region 201b, 201c, etc. has the same predetermined width w, up until the last subdivision 201n. In a case where the predetermined sub-region width divides integrally into the overall width of region 101, then the last sub-region 201n will have the same width as the other sub-regions. Alternatively, as shown in FIG. 2, where the width of region 101 is not an integer multiple of the predetermined sub-region width w, the last subdivision 201n has a smaller width. Due to variations in the height of region 101 across its width, the height of the respective subdivisions 201a to 201n also varies. Accordingly, depending on the overall shape of the region 101 to be subdivided, the area of each subdivision may be different.
The conventional naive method has several downsides. As mentioned, it is possible for the area of each subdivision to vary dramatically. This can undermine the goal of having relatively uniform regions. Also, the sub-regions are not compact, and the perimeters of each are longer than they would need to be. Also, without more information, it is unknown whether the x- or y-axis is a meaningful axis for splitting. For instance, in the case of aerial imagery of a farmer's field, the orientation of the region may be based on how the image was collected (e.g., the flight path of a drone), which might not have any useful relationship to the intended organization of information of an analyst reviewing the data. Further, since the naive method only cuts in one direction, it tends toward always making long, skinny zones (or, alternatively short, fat zones). In many cases, the long, skinny (or short, fat) zones created by the naive method are undesirable.
FIG. 3 illustrates the result of a second conventional method (the “fishnet” method) for subdividing region 101, wherein region 101 is repeatedly divided at intervals along the x- and y-axes, which generally creates squares, except along the edges of the region 101. In FIG. 3, region 101 is split vertically and horizontally to form subdivisions 301a, 301b, 301c . . . 301n, where n is an arbitrary integer. Where region 101 completely occupies an interval in both dimensions, the resulting sub-zone has a rectangular shape. Where the region fills less than the entire interval in either dimension, the resulting subregion may have a non-rectangular shape. For example, 301n has a triangular shape.
The fishnet method has several downsides. For one, there is a likelihood that at least some of the zones will be quite small, i.e., much smaller than the desired unit of analysis for a zone. In other words, although the resulting zone is below a threshold size, the resulting zone is so small, that it becomes inefficient for use. As the number of such excessively small zones multiplies, the issue is exacerbated. Hence, the fishnet method has been criticized widely by users of GIS software systems including conventional products that employ the fishnet method.
Accordingly, there is a desire to solve these and other related problems.